package leetcode;

/**
 * @Description
 * @Version V1.0.0
 * @Since 1.0
 * @Date 21.4.26
 */

public class T1011 {

    public static void main(String[] args) {
        T1011 t = new T1011();
        int d = 5;
        int[] weight = new int[]{1,2,3,4,5,6,7,8,9,10};

        System.out.println(t.shipWithinDays(weight, d));
    }

    //方法2 使用二分法，最小值为数组中的最大值，最大值为数组的和，非标准二分
    public int shipWithinDays(int[] weights, int d) {
        Integer l = max(weights);
        Integer r = sum(weights);
        int mid = -1;
        while (l < r) {
            mid = l + r >> 1;
            if (isOK(weights, d, mid)) {
                r = mid;
            } else {
                l++;
            }
        }
        return mid;
    }


    //方法一直接模拟
    public int shipWithinDays1(int[] weights, int d) {
        Integer predict = max(weights);
        while (!isOK(weights, d, predict)) {
            predict++;
        }
        return predict;
    }

    /**
     * 数组中最大的重量
     *
     * @param weight
     * @return
     */
    public Integer max(int[] weight) {
        int max = -1;
        for (int i = 0; i < weight.length; i++) {
            if (max < weight[i]) {
                max = weight[i];
            }
        }
        return max;
    }

    public Integer sum(int[] weight) {
        int sum = 0;
        for (int i = 0; i < weight.length; i++) {
            sum += weight[i];
        }
        return sum;
    }


    /**
     * 在cap容量下能否在d天内将货物运输完成
     *
     * @param weight
     * @param d
     * @param cap
     * @return
     */
    private boolean isOK(int[] weight, int d, int cap) {
        if (split(weight, cap) <= d) {
            return true;
        }
        return false;
    }

    /**
     * 将货物按照cap容量分组，查看能分成几组
     *
     * @param weight
     * @param cap
     * @return
     */
    private int split(int[] weight, int cap) {
        int result = 1;
        int useCap = 0;
        for (int i = 0; i < weight.length; i++) {
            if ((useCap += weight[i]) <= cap) {
                continue;
            } else {
                useCap = weight[i];
                result++;
            }
        }
        return result;
    }


}
